'''
https://leetcode.cn/problems/path-sum-ii/description/
'''
from collections import deque
from typing import Optional, List

from c06_tree.utils import TreeNode


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans = []

        def process(root, aim, path):
            if not root: return
            path.append(root.val)
            aim -= root.val
            if root.left is None and root.right is None:
                if aim == 0:
                    ans.append(list(path))
                path.pop()
                return
            process(root.left, aim, path)
            process(root.right, aim, path)
            path.pop()

        process(root, targetSum, deque())
        return ans
